UVa/10036 - Divisibility/10036.2.cpp

   1 /*
   2   Accepted
   3  */
   4 #include <iostream>
   5
   6 using namespace std;
   7
   8 const int MAXN = 10000, MAXK = 100;
   9
  10 bool dp[MAXN][MAXK];
  11 int a[MAXN];
  12
  13 int main(){
  14   int cases;
  15   cin >> cases;
  16   while (cases--){
  17     int n, k;
  18     cin >> n >> k;
  19     if ( (0 <= n && n <= MAXN && 0 <= k && k <= MAXK) == false ) while (1);
  20     for (int i=0; i<n; ++i){
  21       cin >> a[i];
  22     }
  23
  24     for (int j=0; j<k; ++j){
  25       dp[0][j] = false;
  26     }
  27
  28     int t = a[0];
  29     while (t < 0) t += k;
  30     dp[0][t%k] = true;
  31     for (int i=1; i<n; ++i){
  32       for (int j=0; j<k; ++j){
  33         dp[i][j] = false;
  34         t = j + a[i];
  35         while (t < 0) t += k;
  36         dp[i][j] |= dp[i-1][t%k];
  37
  38         t = j - a[i];
  39         while (t < 0) t += k;
  40         dp[i][j] |= dp[i-1][t%k];
  41       }
  42       }
  43
  44     cout << (dp[n-1][0]?"D":"Not d") << "ivisible" << endl;
  45   }
  46   return 0;
  47 }